package com.leetcode.algorithm.y22.m06;

/**
 * 416. 分割等和子集
 * 
 * https://leetcode.cn/problems/partition-equal-subset-sum/
 * 
 * @author jie.deng
 *
 */
class Question0416Solution01 {

	public boolean canPartition(int[] nums) {
		int len = nums.length;
		int sum = 0;
		for (int i = 0; i < len; i++) {
			sum += nums[i];
		}

		if ((sum & 1) == 1) {
			// 和为奇数，不能分割等和子集
			return false;
		}

		// 转化为0-1背包问题：挑选部分正整数使和等于sum/2。
		int target = (sum >> 1);
		// dp[i][j]表示从数组的 [0, i] 这个子区间内挑选一些正整数，每个数只能用一次，使得这些数的和恰好等于j
		boolean[][] dp = new boolean[len][target + 1];

		// 初始化状态
		dp[0][0] = true;
		if (nums[0] <= target) {
			dp[0][nums[0]] = true;
		}
		if (nums[0] == target) {
			return true;
		} else if (nums[0] < target) {
			dp[0][nums[0]] = true;
		}

		for (int i = 1; i < len; i++) {
			int num = nums[i];
			for (int j = 0; j < target; j++) {
				if (dp[i - 1][j]) {
					dp[i][j] = true;
					if (j + num == target) {
						return true;
					} else if (j + num < target) {
						dp[i][j + num] = true;
					}
				}
			}
		}
		return false;
	}

}